package leetcode;

class Solution {
    public void quick_sort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int left = begin;
        int right = end;
        int key = left;

        while (left < right) {
            while (left < right && arr[right] >= arr[key]) {
                right--;
            }
            while (left < right && arr[left] <= arr[key]) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        int meet = left;
        swap(arr, key, left);
        quick_sort(arr, begin, meet - 1);
        quick_sort(arr, meet + 1, end);
    }

    private void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }

}

public class Test2 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{1, 23, 4, 7, 8, 9, 5, 3, 3};
        solution.quick_sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
